package me.wangshier.leetcode.medium;

/**
 * 18. 小U的最大连续移动次数问题
 *
 * @Author: tongqianwen
 * @Date: 2025/3/10
 */
public class MaximumContinuousMovement {
    private static final int[][] DIRECTIONS = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static int solution(int m, int n, int[][] a) {
        boolean[][] visited = new boolean[m][n];
        int maxStep = 0;


        // 遍历每个起点，尝试上坡和下坡两种情况
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                maxStep = Math.max(maxStep, dfs(visited,new int[]{i, j, 1}, a)); // 从 (i, j) 开始上坡
                maxStep = Math.max(maxStep, dfs(visited, new int[]{i, j, 0},a)); // 从 (i, j) 开始下坡
            }
        }

        return maxStep - 1; // 减去起始点的 1
    }

    public static Integer dfs(boolean[][] visited, int[] params, int[][] a) {
        int x = params[0];
        int y = params[1];
        boolean up = params[2] == 1;

        int maxPath = 0;

        // 标记当前位置已访问
        visited[x][y] = true;

        // 尝试向四个方向移动
        for (int[] dir : DIRECTIONS) {
            int nextX = x + dir[0];
            int nextY = y + dir[1];

            // 检查是否越界，是否已访问
            int m = a.length;
            int n = a[0].length;
            if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextX][nextY]) {
                // 检查是否满足上/下坡条件
                if ((up && a[nextX][nextY] < a[x][y]) || (!up && a[nextX][nextY] > a[x][y])) {
                    maxPath = Math.max(maxPath, dfs(visited, new int[]{nextX, nextY, up ? 0 : 1},a));
                }
            }
        }

        // 回溯，清除标记
        visited[x][y] = false;

        return maxPath + 1;
    }

    public static void main(String[] args) {
        System.out.println(solution(2, 2, new int[][]{{1, 2}, {4, 3}}) == 3);
        System.out.println(solution(3, 3, new int[][]{{10, 1, 6}, {5, 9, 3}, {7, 2, 4}}) == 8);
        System.out.println(solution(4, 4, new int[][]{{8, 3, 2, 1}, {4, 7, 6, 5}, {12, 11, 10, 9}, {16, 15, 14, 13}}) == 11);
    }
}
